#pragma once
#include<iostream>
#include<stdlib.h>
#include<vector>
#include<time.h>
#include<assert.h>
#include<mutex>
#include<thread>
#include<algorithm>
#include<unordered_map>
#include"ObjectPool.h"
using std::cout;
using std::endl;

#ifdef _WIN32
#include <windows.h>
#else
// ...
#endif

static const size_t NFREE_LIST = 208;
static const size_t MAX_BYTES = 256 * 1024;
static const size_t PAGA_LIST = 129;
static const size_t PAGE_SHIFT = 13;


//条件编译
#ifdef _WIN64
typedef size_t PageID;
#elif _WIN32
typedef unsigned long long PageID;

#endif

inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
	void* ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
	// linux下brk mmap等
#endif

	if (ptr == nullptr)
		throw std::bad_alloc();

	return ptr;
}

inline static void SystemFree(void* ptr)
{
#ifdef _WIN32
	VirtualFree(ptr, 0, MEM_RELEASE);
#else
	// sbrk unmmap等
#endif
}

//管理内存块的链表
class FreeList
{
public:
	void Push(void* obj)
	{
		assert(obj);
		//头插-->对于一个自由链表，当我们用完了之后，还回来可以头插
		*(void**)obj = _freelist;
		_freelist = obj;

		_count++;
	}
	void PushRange(void* start, void* end,size_t n)
	{
		assert(start && end);
		*(void**)end = _freelist;
		_freelist = start;

		_count += n;

	}
	void* Pop()
	{
		assert(_freelist);
		//头删-->对于一个自由链表，当我们需要用到这块内存时，头删掉一块内存。
		void* obj = _freelist;
		_freelist = *(void**)obj;

		*(void**)obj = nullptr;
		_count--;
		return obj;
	}
	void PopRange(void*& start, void*& end, size_t num)
	{
		start = _freelist;
		end = start;
		for (size_t i = 0; i < num-1; i++){
			end = *(void**)end;
		}
		_freelist = *(void**)end;
		*(void**)end = nullptr;
		_count -= num;
	}

	bool Empty()
	{
		//当我们要使用这块自由链表上的内存块时，先要判断这块自由链表是否还有剩余的内存块
		return _freelist == nullptr;
	}
	size_t& MaxSize()
	{
		return _size;
	}
	size_t _Count()
	{
		return _count;
	}
private:
	void* _freelist=nullptr;
	size_t _size=1;
	size_t _count = 0;
};

//计算
class SizeClass
{
public:
	//对齐规则
	// 整体控制在最多10%左右的内碎片浪费
	// [1,128]					8byte对齐	    freelist[0,16)
	// [128+1,1024]				16byte对齐	    freelist[16,72)
	// [1024+1,8*1024]			128byte对齐	    freelist[72,128)
	// [8*1024+1,64*1024]		1024byte对齐     freelist[128,184)
	// [64*1024+1,256*1024]		8*1024byte对齐   freelist[184,208)
	//通过哈希映射来找到相对于的桶，我们写内存池最主要的原因是为了提高了效率，
	//先提前开好内存，等到要用到时候来分配
	//对于这种分配方法，我们可以8byte来分，但是这也就需要256*1024/8个桶，太多了没必要。
	//所以，我们可以通过上面已经算好了的规则来分配
	
	//计算对齐数，方便在central cache上拿
	//为什么使用静态内联呢？
	//
	static inline size_t _RoundUp(size_t bytes, size_t alignNum)
	{
		return ((bytes+ alignNum - 1) & ~(alignNum - 1));
	}
	static inline size_t RoundUp(size_t size)
	{
		assert(size >0);

		if (size <= 128){
			return _RoundUp(size, 8);
		}
		else if (size <= 1024){
			return _RoundUp(size, 16);
		}
		else if (size <=8 * 1024){
			return _RoundUp(size, 128);
		}
		else if (size <= 64 * 1024){
			return _RoundUp(size, 1024);
		}
		else if (size <= 256 * 1024){
			return _RoundUp(size, 8*1024);
		}
		else if (size > 256 * 1024){
			return _RoundUp(size, 1 << PAGE_SHIFT);
		}
		else{
			assert(false);
			return -1;
		}
	}
	/*static inline size_t _Index(size_t size, size_t alignNum)
	{
		if (size % alignNum == 0){
			return size % alignNum+1;
		}
		else{
			return size % alignNum;
		}

	}*/
	static inline size_t _Index(size_t bytes, size_t align_shift)
	{
		return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
	}

	static inline size_t Index(size_t size)
	{
		assert(size <= MAX_BYTES);

		static int group_array[4] = { 16, 56, 56, 56 };
		if (size <= 128){
			return _Index(size, 8);
		}
		else if (size <= 1024){
			return _Index(size-128, 16)+group_array[0];
		}
		else if (8 * 1024){
			return _Index(size-1024, 128) + group_array[1]+group_array[0];
		}
		else if (64 * 1024){
			return _Index(size-8*1024, 1024) + group_array[2]+group_array[1]+group_array[0];
		}
		else if (256 * 1024){
			return _Index(size-64*1024, 8 * 1024) + group_array[3]+group_array[2]+group_array[1]+group_array[0];
		}
		else{
			assert(false);
			return -1;
		}
	}
	static size_t NumMoveSize(size_t size)
	{
		assert(size > 0);

		// [2, 512]，一次批量移动多少个对象的(慢启动)上限值
		// 小对象一次批量上限高
		// 小对象一次批量上限低
		int num = MAX_BYTES / size;
		if (num < 2)
			num = 2;

		if (num > 512)
			num = 512;

		return num;
	}
	static size_t NumMovePaga(size_t size)
	{
		size_t num = NumMoveSize(size);
		size_t npage = num*size;

		npage >>= PAGE_SHIFT;
		if (npage == 0)
			npage = 1;

		return npage;
	}
	
};

//在设计central cache时，这个是线程共享的

//描述页的结构
class Span
{
public:
	//页号，在32位上和64位上是不同的
	PageID _pageId = 0;
	//页的数量
	size_t n=0;
	//页的指针—》双向循环链表来组织的
	Span* next=nullptr;
	Span* prev=nullptr;
	//页块指针
	void* _spanlist=nullptr;
	//对象使用页块的个数
	size_t _usecount=0;
	//……
	bool state = false;
	//对象的大小
	size_t objSize = 0;
};

class SpanList
{
public:
	SpanList(){
		_head = new Span();
		_head->next = _head;
		_head->prev = _head;
	}
	Span* Begin()
	{
		return _head->next;
	}
	Span* End()
	{
		return _head;
	}
	bool Empty()
	{
		return _head->next == _head;
	}
	/*size_t size(){return}*/
	//插入->自己计算在哪插入
	void Insert(Span* pos,Span* newspan)
	{
		assert(pos);
		assert(newspan);
		Span* cur = pos->prev;
		cur->next = newspan;
		pos->prev = newspan;

		newspan->next = pos;
		newspan->prev = cur;

	}
	//删除
	void Erase(Span* newspan)
	{
		assert(newspan);
		assert(newspan != _head);
		Span* cur = newspan->prev;
		Span* pos = newspan->next;

		cur->next = pos;
		pos->prev = cur;
		//不用delete,这个删除的空间要给page cache
	}
	void PushFront(Span* span)
	{
		Insert(Begin(), span);
	}

	Span* PopFront()
	{
		Span* front = _head->next;
		//Span* front = _head;
		Erase(front);
		return front;
	}
private:
	Span* _head;
public:
	std::mutex mtx;//桶锁
};


